package RBTree;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ling
 * Date: 2022-11-23
 * Time: 19:34
 */

import AVLTree.AVLTree;
import com.sun.org.apache.regexp.internal.RE;

import static RBTree.COLOR.BLACK;
import static RBTree.COLOR.RED;

/**
 * 红黑树实现
 */
public class RBTree {
    static class RBTreeNode {
        public RBTreeNode left;
        public RBTreeNode right;
        public RBTreeNode parent;
        public COLOR color;//结点颜色;
        public int val;

        public RBTreeNode(int val) {
            this.val = val;
            this.color = RED;
        }
    }
    public RBTreeNode root;
    public boolean insert(int val) {
        RBTreeNode node = new RBTreeNode(val);
        if(root == null) {
            root = node;
            root.color = COLOR.BLACK;
            return true;
        }
        //寻找插入位置
        RBTreeNode parent = null;
        RBTreeNode cur = root;
        while(cur!=null) {
            if(cur.val<val) {
                parent = cur;
                cur = cur.right;
            } else if (cur.val>val) {
                parent = cur;
                cur = cur.left;
            } else {
                return false;
            }
        }
        //到这里cur = null
        if(parent.val>val) {
            parent.left = node;
        } else {
            parent.right = node;
        }
        node.parent = parent;
        cur = node;
        //到这里【向上调整颜色】
        //新插入的结点为红色的，如果父亲节点也是红色，就需要调整
        while(parent!=null&&parent.color== RED) {
            //parent是红色的，所以parent必有父亲节点
            RBTreeNode grandparent = parent.parent;
            //情况1.0 parent是grandparent的左孩子
            if(parent==grandparent.left) {
                RBTreeNode uncle = grandparent.right;
                //情况1.1 cur为红色，parent为红色 grandparent为黑色,uncle存在且为红色，
                if(uncle!=null&&uncle.color== RED) {
                    parent.color = COLOR.BLACK;
                    uncle.color = COLOR.BLACK;
                    grandparent.color = RED;//先变成红色，然后不是根节点，继续向上调整，如果为根节点
                    cur =grandparent;
                    parent = cur.parent;
                } else {
                    //情况1.3 cur为红，parent为红，grandparent为黑色，uncle不存在或者uncle为黑色，cur为parent右孩子
                    if(cur==parent.right) {
                        //先左旋
                        rotateLeft(parent);
                        //交换cur和parent的引用
                        RBTreeNode tmp = parent;
                        parent = cur;
                        cur = tmp;
                        //然后就变成情况1.2
                    }
                    //情况1.2 cur为红，parent为红，grandparent为黑色，uncle不存在或者uncle为黑色，cur为parent左孩子
                    //对grandparent右旋
                    rotateRight(grandparent);
                    //在修改颜色
                    grandparent.color = RED;
                    parent.color = COLOR.BLACK;
                }
            } else {
                //情况2.0 parent是grandparent的右孩子 parent == grandparent.right
                RBTreeNode uncle = grandparent.left;
                //情况2.1 cur为红色，parent为红色 grandparent为黑色,uncle存在且为红色，
                if(uncle!=null&&uncle.color== RED) {
                    parent.color = COLOR.BLACK;
                    uncle.color = COLOR.BLACK;
                    grandparent.color = RED;
                    cur = grandparent;
                    parent = cur.parent;
                } else {
                    //情况2.3 cur为红，parent为红，grandparent为黑色，uncle不存在或者uncle为黑色，cur为parent左孩子
                    if(cur == parent.left) {
                        //先右旋
                        rotateRight(parent);
                        //交换cur和parent的引用
                        RBTreeNode tmp = parent;
                        parent = cur;
                        cur = tmp;
                    }
                    //情况2.2 cur为红，parent为红，grandparent为黑色，uncle不存在或者uncle为黑色，cur为parent右孩子
                    //对grandparent左旋
                    rotateLeft(grandparent);
                    //修改颜色
                    grandparent.color = RED;
                    parent.color = BLACK;
                }
            }
        }
        //最后将根节点修改为黑色
        root.color = COLOR.BLACK;
        return true;
    }

    /**
     * 左旋
     * @param parent
     */
    private void rotateLeft(RBTreeNode parent) {
        RBTreeNode subR = parent.right;
        RBTreeNode subRL = subR.left;
        //记录一下parent的父亲节点
        RBTreeNode pParent = parent.parent;
        parent.right = subRL;
        //检查有没有subRL
        if(subRL!=null) {
            subRL.parent = parent;
        }
        subR.left = parent;
        parent.parent = subR;
        //检查当前是不是根节点
        if(parent==root) {
            root = subR;
            root.parent = null;
        } else {
            if(pParent.left == parent) {
                pParent.left = subR;
            } else {
                pParent.right = subR;
            }
            subR.parent = pParent;
        }

    }

    /**
     * 右旋
     * @param parent
     */
    private void rotateRight(RBTreeNode parent) {
        RBTreeNode subL = parent.left;
        RBTreeNode subLR=subL.right;
        //记录一下parent的父亲节点
        RBTreeNode pParent = parent.parent;
        parent.left = subLR;
        //检查有没有subLR
        if(subLR!=null) {
            subLR.parent = parent;
        }
        subL.right = parent;
        parent.parent = subL;
        //检查当前是不是根节点
        if(parent == root) {
            root = subL;
            root.parent = null;
        } else {
            //不是根节点，判断这棵子树是左子树还是右子树
            if(pParent.left == parent) {
                pParent.left = subL;
            } else {
                pParent.right = subL;
            }
            subL.parent = pParent;
        }

    }

    /**
     * 检查一颗树是否为红黑树
     * @return
     */
    public boolean isRBTree() {
        if(root == null) {
            //如果一颗树是空树，那么这颗树就是红黑树
            return true;
        }
        if(root.color!=BLACK) {
            System.out.println("违反了性质；根节点必须是黑色的");
        }
        //计算最左边路径上的黑色结点个数
        int blackNum = 0;
        RBTreeNode cur = root;
        while(cur!=null) {
            if(cur.color==BLACK) {
                blackNum++;
            }
            cur = cur.left;
        }


        // 检查有没有连续出现两个红色的结点&&检查每条路径上的黑色结点是否相同
        return checkRedColor(root)&&checkBlackNum(root,0,blackNum);
    }

    /**
     * 检查有没有连续出现两个红色的结点
     * @param root
     * @return
     */
    private boolean checkRedColor(RBTreeNode root) {
        if(root == null) {
            return true;
        }
        if(root.color == RED) {
            RBTreeNode parent = root.parent;
            if(parent.color==RED) {
                System.out.println("违反了性质，连续出现了两个红色的结点");
                return false;
            }
        }
        return checkRedColor(root.left)&&checkRedColor(root.right);
    }

    /**
     * 检查每条路径上的黑色结点是否相同
     * pathBlackNum:每次递归是，计算黑色节点的个数
     * blackNum:事先计算好的一条路径上的黑色结点
     * @param root
     * @param pathBlackNum
     * @param blackNum
     * @return
     */
    private boolean checkBlackNum(RBTreeNode root,int pathBlackNum,int blackNum) {
        if(root==null) {
            return true;
        }
        if(root.color==BLACK) {
            pathBlackNum++;
        }
        if(root.left==null&&root.right==null) {
            if(pathBlackNum!=blackNum) {
                System.out.println("违反了性质，某条路径上黑色的结点个数不一样");
                return false;
            }
        }
        return checkBlackNum(root.left,pathBlackNum,blackNum)&&checkBlackNum(root.right,pathBlackNum,blackNum);
    }
    public void inorder(RBTreeNode root) {
        if(root==null) {
            return;
        }
        inorder(root.left);
        System.out.println(root.val);
        inorder(root.right);
    }
    public static void main(String[] args) {
        int[] array = {4,2,6,1,3,5,15,7,16,14};
        RBTree rbTree = new RBTree();
        for(int i=0;i<array.length;i++) {
            rbTree.insert(array[i]);
        }
        System.out.println(rbTree.isRBTree());
        rbTree.inorder(rbTree.root);
    }
}
